package com.sdll.algorithm;

import java.util.Date;
import java.util.Scanner;

public class PlalindromeMax {
	
	public static void main(String[] args) {
		Date beginDate = new Date(); 
		Scanner scanner = new Scanner(System.in);
//		String str = scanner.next();
//		String str = "zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk";
		String str = "ambcdba";
		int deNum = testMaxLongPlalindrome(str);
		int deNum1 = maxLCS(str);
		Date endDate = new Date(); 
//		System.out.println(deNum );
//		System.out.println("需要删除的数：" + deNum + "总花费时间：" + (endDate.getTime()-beginDate.getTime())/1000);
	}
	
	/**
	 * 测试最长的回文串
	 * 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
	 * 输出需要删除的字符个数。
     * @param str 待测试字符串
	 * @return
	 */
	public static int maxLCS(String string) {
		System.out.println(string + "========maxLCS====================");
		char[] chars = string.toCharArray();
		int length = string.length();
		int dp[][] = new int[length+1][length+1];
		for(int i=0; i<length; i++){
			for(int j=0; j<length; j++){
//				System.out.print("chars["+i+"] == chars["+(length-j - 1)+"] : " + (chars[i] == chars[length - j - 1]));
				if(chars[i] == chars[length - j - 1]){
					dp[i+1][j+1] = dp[i][j] + 1;
				}else{
					dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]) > dp[i][j] ? 
							Math.max(dp[i][j+1],dp[i+1][j]) : dp[i][j];
				}
//				System.out.println("\t dp["+(i+1)+"]["+(j+1)+"] = " + dp[i+1][j+1]);
			}
		}
		
		for (int i = 0; i <= length; i++) {
			for (int j = 0; j <= length; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println(length - dp[length][length]);
		return 0;
	}
	
	public static int testMaxLongPlalindrome(String str) {
		System.out.println(str + "========testMaxLongPlalindrome====================");
		int length = str.length();
		String[] charstr = str.split("");
		int[][] dp = new int[length + 1][length + 1];
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if(charstr[i].equals(charstr[length - j - 1])) {
					dp[i + 1][j + 1] = dp[i][j] + 1;
				}else {
					dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
				}
			}
		}
		
		for (int i = 0; i <= length; i++) {
			for (int j = 0; j <= length; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println(length - dp[length][length]);
		
		return 0;
	}

}
